# 实现获取 下一个排列 的函数，算法需要将给定数字序列重新排列成字典序中下一个更大的排列（即，组合出下一个更大的整数）。 
# 
#  如果不存在下一个更大的排列，则将数字重新排列成最小的排列（即升序排列）。 
# 
#  必须 原地 修改，只允许使用额外常数空间。 
# 
#  
# 
#  示例 1： 
# 
#  
# 输入：nums = [1,2,3]
# 输出：[1,3,2]
#  
# 
#  示例 2： 
# 
#  
# 输入：nums = [3,2,1]
# 输出：[1,2,3]
#  
# 
#  示例 3： 
# 
#  
# 输入：nums = [1,1,5]
# 输出：[1,5,1]
#  
# 
#  示例 4： 
# 
#  
# 输入：nums = [1]
# 输出：[1]
#  
# 
#  
# 
#  提示： 
# 
#  
#  1 <= nums.length <= 100 
#  0 <= nums[i] <= 100 
#  
#  Related Topics 数组 双指针 
#  👍 1344 👎 0


from typing import List


# leetcode submit region begin(Prohibit modification and deletion)
class Solution:
    def nextPermutation(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        i = len(nums) - 2
        while i >= 0 and nums[i] >= nums[i+1]:
            i -= 1
        if i >= 0:
            j = len(nums) - 1
            while j >= 0 and nums[j] <= nums[i]:
                j -= 1
            nums[i], nums[j] = nums[j], nums[i]

        left, right = i + 1, len(nums) - 1
        while left < right:
            nums[left], nums[right] = nums[right], nums[left]
            left += 1
            right -= 1


# leetcode submit region end(Prohibit modification and deletion)


def log(*args, **kwargs):
    print(*args, **kwargs)


# 两遍扫描
# 变大排列: 将左边的较小数和右边的较大数交换
# 左边的较小数尽量靠右, 右边的较大数, 尽可能小
# 具体: 找到下降排列, 前一个数为较小数; 从右向左, 找到下降序列中第一个大于较小数, 交换后翻转下降序列
#
#     def nextPermutation(self, nums: List[int]) -> None:
#         """
#         Do not return anything, modify nums in-place instead.
#         """
#         i = len(nums) - 2
#         while i >= 0 and nums[i] >= nums[i + 1]:
#             i -= 1
#         # 找不到i , 序列降序, 不需要找j, 只需要翻转
#         if i >= 0:
#             j = len(nums) - 1
#             while j >= 0 and nums[j] <= nums[i]:
#                 j -= 1
#             nums[i], nums[j] = nums[j], nums[i]
#
#         # 翻转下降序列
#         left, right = i + 1, len(nums) - 1
#         while left < right:
#             nums[left], nums[right] = nums[right], nums[left]
#             left += 1
#             right -= 1

if __name__ == '__main__':
    s = Solution()
    # n1 = [1, 2, 3]
    # s.nextPermutation(n1)
    # e1 = [1, 3, 2]
    # assert e1 == n1, n1
    #
    # n2 = [1, 1, 5]
    # s.nextPermutation(n2)
    # e2 = [1, 5, 1]
    # assert n2 == e2, n2
    #
    n3 = [3, 2, 1]
    s.nextPermutation(n3)
    log(n3)
    e3 = [1, 2, 3]
    assert n3 == e3, n3
